package 剑指offer;

public class _51数组中的逆序对 {
    public int reversePairs(int[] nums){
        int length = nums.length;
        //数组中只有一个元素或没有元素，逆序对为0
        if (length < 2){
            return 0;
        }
        //题目没有让给nums排序，所以我们需要拷贝出来一份nums数组
        int[] copy = new int[length];
        for (int i = 0; i < length; i++) {
            copy[i] = nums[i];
        }
        //临时数组
        int[] temp = new int[length];
        return reversePairs(copy, 0, length - 1, temp);
    }
    /**
     *num[left...right]计算逆序对个数并排序
     * @param copy 写回拷贝数组
     * @param left
     * @param right
     * @param temp 临时数组
     * @return
     */
    private int reversePairs(int[] copy, int left, int right, int[] temp) {
        if(left == right){
            return 0;
        }
        //预防溢出
        int mid = left + (right - left) / 2;
        //分左半区间
        int leftPairs = reversePairs(copy, left, mid ,temp);
        //分右半区间
        int rightPairs = reversePairs(copy, mid + 1, right, temp);

        //左半区间最后一个元素值大于右半区间第一个元素值，不需要merge，直接就是有序的
        //也就不可能有逆序对了
        if (copy[mid] <= copy[mid + 1]){
            return leftPairs + rightPairs;
        }
        //merge并且计数
        int crossPairs = mergeAndCount(copy, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    /**
     * copy[left...mid]有序，copy[mid + 1...right]有序
     * 合并他们并且算逆序对个数
     * @param copy
     * @param left
     * @param mid
     * @param right
     * @param temp
     * @return
     */
    private int mergeAndCount(int[] copy, int left, int mid, int right, int[] temp) {
        //先进行数组拷贝
        for (int i = left; i <= right; i++) {
            temp[i] = copy[i];
        }
        //左半区间第一个元素
        int i = left;
        //右半区间第一个元素
        int j = mid + 1;
        //排序，写回copy

        int count = 0;
        for (int k = left; k <= right; k++) {
            if (i == mid + 1){
                copy[k] = temp[j];
                j ++;
            }else if (j == right + 1){
                copy[k] = temp[i];
                i ++;
            }else if(temp[i] <= temp[j]){
                copy[k] = temp[i];
                i ++;
            }else {
                copy[k] = temp[j];
                j ++;
                count += (mid - i + 1);
            }
        }
        return count;
    }
}
